/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright (c) 2013-2014 sagyf Yang. The Four Group.
 */

package app.kits;

import com.github.sog.kit.Tuple;
import com.google.common.collect.Lists;

import java.util.List;
import java.util.Vector;

/**
 * <p>
 * .
 * </p>
 *
 * @author sagyf yang
 * @version 1.0 2014-04-26 13:52
 * @since JDK 1.6
 */
public class ParkingMapKit {

    //节点关闭列表
    final Vector<ParkingNode> closeNode = new Vector<ParkingNode>();
    //节点开启别表
    final Vector<ParkingNode> openNode  = new Vector<ParkingNode>();

    //每个图块G值的增加值
    private final byte G_OFFSET = 1;
    //图块大小
    private final byte tileSize;
    //可以通行的地图图块索引
    private byte canMoveIndex = 0;

    private int rows = 0;            //地图行数
    private int cols = 0;            //地图列数
    private byte[][] map;        //地图数据
    private int      destinationRow;    //目标所在行
    private int      destinationCol;    //目标所在列

    private ParkingMapKit(byte tileSize) {
        this.tileSize = tileSize;
    }

    public static ParkingMapKit create() {
        byte size = 6;
        return new ParkingMapKit(size);
    }

    public static ParkingMapKit createB2() {
        byte size = 15;
        return new ParkingMapKit(size);
    }

    //设置地图信息属性
    public void setMap(byte[][] map, int rows, int cols) {
        this.map = map;
        this.rows = rows;
        this.cols = cols;
        closeNode.removeAllElements();
        openNode.removeAllElements();
    }

    public List<Tuple<Integer, Integer>> getPath(int startX, int StartY, int destinationX, int destinationY) {
        final List<Tuple<Integer, Integer>> roads = Lists.newArrayList();
        destinationRow = getRowPosition(destinationY);
        destinationCol = getColPosition(destinationX);
        ParkingNode startNode = new ParkingNode();
        startNode.row = getRowPosition(StartY);
        startNode.col = getColPosition(startX);
        startNode.g = 0;
        startNode.h = getH(startNode.row, startNode.col);
        startNode.f = startNode.g + startNode.h;
        openNode.add(startNode);
        ParkingNode bestNode;
        while (true) {
            bestNode = getBesetNode();
            if (bestNode == null) {        //未找到路径
                return null;
            } else if (bestNode.row == getRowPosition(destinationY)
                    && bestNode.col == getColPosition(destinationX)) {
//                long time = System.currentTimeMillis() - timer;
                ParkingNode _Node = bestNode;
                while (_Node.parent != null) {
                    roads.add(new Tuple<Integer, Integer>(_Node.col * tileSize, _Node.row * tileSize));
                    _Node = _Node.parent;
                }
                return roads;
            }
            seachSeccessionNode(bestNode);
        }
    }

    /**
     * 根据传入的节点生成子节点
     *
     * @param bestNode bestNode
     */
    private void seachSeccessionNode(ParkingNode bestNode) {
        int row, col;
        //上部节点
        if (isCanMove(row = bestNode.row - 1, col = bestNode.col)) {
            creatSeccessionNode(bestNode, row, col);
        }
        //下部节点
        if (isCanMove(row = bestNode.row + 1, col = bestNode.col)) {
            creatSeccessionNode(bestNode, row, col);
        }
        //左部节点
        if (isCanMove(row = bestNode.row, col = bestNode.col - 1)) {
            creatSeccessionNode(bestNode, row, col);
        }
        //右部节点
        if (isCanMove(row = bestNode.row, col = bestNode.col + 1)) {
            creatSeccessionNode(bestNode, row, col);
        }
        closeNode.addElement(bestNode);
        for (int i = 0; i < openNode.size(); i++) {
            if (openNode.elementAt(i).row == bestNode.row
                    && openNode.elementAt(i).col == bestNode.col) {
                openNode.removeElementAt(i);
                break;
            }
        }
    }

    private void creatSeccessionNode(ParkingNode bestNode, int row, int col) {
        ParkingNode oldNode;
        int g = bestNode.g + G_OFFSET;
        if (!isInClose(row, col)) {
            if ((oldNode = checkOpen(row, col)) != null) {
                if (oldNode.g < g) {
                    oldNode.parent = bestNode;
                    oldNode.g = g;
                    oldNode.f = g + oldNode.h;
                }
            } else {
                ParkingNode node = new ParkingNode();
                node.parent = bestNode;
                node.g = g;
                node.h = getH(row, col);
                node.f = node.g + node.h;
                node.row = row;
                node.col = col;
                openNode.addElement(node);
            }
        }
    }


    private ParkingNode checkOpen(int row, int col) {
        ParkingNode node;
        for (int i = 0; i < openNode.size(); i++) {
            if (openNode.elementAt(i).row == row && openNode.elementAt(i).col == col) {
                node = openNode.elementAt(i);
                return node;
            }
        }
        return null;
    }

    private boolean isInClose(int row, int col) {
        for (int i = 0; i < closeNode.size(); i++) {
            if (closeNode.elementAt(i).row == row && closeNode.elementAt(i).col == col) {
                return true;
            }
        }
        return false;
    }

    //得到最优节点
    private ParkingNode getBesetNode() {
        ParkingNode bestNode = null;
        int f = 999999999;
        for (int i = 0; i < openNode.size(); i++) {
            if (openNode.elementAt(i).f < f) {
                f = openNode.elementAt(i).f;
                bestNode = openNode.elementAt(i);
            }
        }
        return bestNode;
    }

    //得到该图块的H值
    private int getH(int row, int col) {
        return (Math.abs(destinationRow - row) + Math.abs(destinationCol - col));
    }

    //得到该位置所在地图行
    private int getRowPosition(int y) {
        return (y / tileSize);
    }

    //得到该位置所在地图列
    private int getColPosition(int x) {
        return (x / tileSize);
    }

    //检测该图块是否可通行
    private boolean isCanMove(int col, int row) {
        return !(col < 0 || col >= cols) && !(row < 0 || row >= rows) && map[col][row] == canMoveIndex;
    }

}

/**
 * 节点类
 */
class ParkingNode {

    int f;    //该节点路径评分

    int g;    //从起始点到该节点的预估距离

    int h;    //从该节点到终点的曼哈顿距离（忽略障碍水平垂直移动到终点的距离）

    int row;    //该节点所在行

    int col;    //该节点所在列

    ParkingNode parent;    //该节点的父节点

    ParkingNode[] child = new ParkingNode[8];    //该节点的子节点，最多8个
}
